package org.example.Soution003;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class GreedilyStringCut {
    public static void main(String[] args) {
        GreedilyStringCut gs = new GreedilyStringCut();
        System.out.println(gs.partitionLabels("eccbbbbdec"));
    }

    public List<Integer> partitionLabels(String s) {
        List<Integer> res=new ArrayList<>();
        char[] chars=s.toCharArray();
        //维护一个list用来存储字母出现的顺序，维护两个map用来存储他们的起点和最大终点
        List<Character> charList=new ArrayList<>();
        Map<Character,Integer> start=new HashMap<>();
        Map<Character,Integer> end=new HashMap<>();
        for(int i=0;i<chars.length;i++) {
            if(!start.containsKey(chars[i])) {
                charList.add(chars[i]);
                start.put(chars[i],i);
                end.put(chars[i],i);
            }else{
                end.put(chars[i],i);
            }
        }
        int flag=0;
        int[] range=new int[]{start.get(charList.get(flag)),end.get(charList.get(flag))};
        flag++;
        while(flag<charList.size()) {
            int curStart=start.get(charList.get(flag));
            int curEnd=end.get(charList.get(flag));
            if(curStart>=range[0] && curStart<=range[1]) {
                range[1]=Math.max(curEnd,range[1]);
            }else{
                res.add(range[1]-range[0]+1);
                range[0]=curStart;
                range[1]=curEnd;
            }
            flag++;
        }
        res.add(range[1]-range[0]+1);
        return res;
    }
}
